Two Snuke
question (e.g. on a test)
https://gyazo.com/f9dd32211e6deb0099516ea09a18ca4f
N is given by the problem condition.
For n less than or equal to N, divide it into 5 numbers
Focusing on this one, let m be the number
Divide this m into two numbers i, j
$ i + j = m
where the constraint [$ 0 \le i < j
I want to find the sum of the differences for all possible i,j
$ f(m) = \sum_{i,j} j - i
I sought it on my own up to this point, but I couldn't figure out where to go from here.
code:python
def f(x):
return (x + x % 2) * ((x + 2) // 2) // 2
Solving with formal power series
Since this function f is a function that takes natural numbers as arguments, it can be interpreted as a sequence of numbers
$ F = \sum_{m=0}^\infty f(m)
My implementation of f would have caused a remainder or truncation, but if we can express this in rational expressions, we can use the formal power series tool.
Observe a sequence of numbers
code:python
array([ 0, 1, 2, 4, 6, 9, 12, 16, 20, 25, 30,
36, 42, 49, 56, 64, 72, 81, 90, 100, 110, 121,
132, 144, 156, 169, 182, 196, 210, 225, 240, 256, 272,
289, 306, 324, 342, 361, 380, 400, 420, 441, 462, 484,
506, 529, 552, 576, 600, 625, 650, 676, 702, 729, 756,
784, 812, 841, 870, 900, 930, 961, 992, 1024, 1056, 1089,
1122, 1156, 1190, 1225, 1260, 1296, 1332, 1369, 1406, 1444, 1482,
1521, 1560, 1600, 1640, 1681, 1722, 1764, 1806, 1849, 1892, 1936,
1980, 2025, 2070, 2116, 2162, 2209, 2256, 2304, 2352, 2401, 2450,
2500])
I'm writing the general term in code, so I know that even-oddness affects it, so I'll try to separate them.
code:python
array([ 0, 2, 6, 12, 20, 30, 42, 56, 72, 90, 110,
132, 156, 182, 210, 240, 272, 306, 342, 380, 420, 462,
506, 552, 600, 650, 702, 756, 812, 870, 930, 992, 1056,
1122, 1190, 1260, 1332, 1406, 1482, 1560, 1640, 1722, 1806, 1892,
1980, 2070, 2162, 2256, 2352, 2450])
array([ 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121,
144, 169, 196, 225, 256, 289, 324, 361, 400, 441, 484,
529, 576, 625, 676, 729, 784, 841, 900, 961, 1024, 1089,
1156, 1225, 1296, 1369, 1444, 1521, 1600, 1681, 1764, 1849, 1936,
2025, 2116, 2209, 2304, 2401, 2500])
At the time of this observation, maspy wrote that $ F = \frac{P}{(1-x^2)^3} was fixed, but I didn't understand it, so I'll bite
sequence of numbers skipped one by one
1, 0, 1, 0, ... How to express the sequence of numbers "0, 0, 1, 0, ..." in terms of a formal power series
If we naively write the equation
$ G = 1 + x^2 + x^4 + \ldots = \sum_{n=0}^\infty x^{2n}
[Infinite sum compression using the inverse of a formal power series
$ G = 1 + x^2 + x^4 + \ldots
$ x^2G = x^2 + x^4 + \ldots
$ (1-x^2)G = 1
$ G = 1/(1-x^2)
One skipped square number
0, 1, 0, 4, 0, 9, ... How to express the sequence of numbers "0, 0, 4, 0, 0, 9, ..." in terms of a formal power series
This is $ H = \sum_{n=0}^\infty ((n+1) / 2)^2 x^n with only the odd-numbered th taken
Note that I was confused as to whether the number sequence was 1-origin or 0-origin, so I aligned it with 0.
Pulled $ F - H.
code:python
array([-0.25, 0. , -0.25, 0. , -0.25, 0. , -0.25, 0. , -0.25,
0. , -0.25, 0. , -0.25, 0. , -0.25, 0. , -0.25, 0. ,...
That is, $ F = G / 4 + H.
Since the calculation is tedious, let's multiply everything by 4 and assume 4H=J.
$ 4F = G + J
$ J = \sum_{n=0}^\infty (n+1)^2 x^n
The first time I did it, I was doing a miscalculation, and it gave me an incorrect equation down the road. code:python
array([ 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169,
196, 225, 256, 289, 324, 361, 400])
array([ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33,
35, 37, 39])
Out37: array(1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2) Out38: array(1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0) $ J = \frac{1 + x}{(1-x)^3}
Did (1-x)^3 correspond to taking the difference three times?
$ 4F = G + J = \frac{1}{1-x^2} + \frac{1 + x}{(1-x)^3} = \frac{(1 - x)^2 + (1 + x)^2}{(1 + x)(1 - x)^3} = \frac{4x}{(1 + x)(1 - x)^3}
I need a simpler formula.
The product of a formal power series is the convolution of a sequence
Using np.convolve, the calculation can be done in one line.
code:python
array([ 0, 1, 0, 0, 0, 0, 0, 0, 0, ...
Multiplying (1 - x)(1 - x)(1 - x)(1 - x)(1 + x) leaves x
$ \frac{x}{(1-x)^3(1+x)}
Did I make a miscalculation along the way? I will verify later.
By the way, I multiplied $ (1-x^2)^3 as maspy originally said, and got this
code:python
In 121: reduce(np.convolve, 1, 0, -1], 1, 0, -1, [1, 0, -1, fs) array([ 0, 1, 2, 1, 0, 0, 0, 0, 0, ...
$ \frac{x(1 + 2 x + x^2)}{(1-x^2)^3} = \frac{x(1 + x)^2}{(1-x)^3(1+x)^3} = \frac{x}{(1-x)^3(1 + x)}
Sort it out and the result is the same.
Suppose F is obtained.
$ F = \frac{x}{(1-x)^3(1+x)}
F was a power series for one of the five separate blocks.
This could be interpreted as a function with m as an argument, and the answer was when the sum was m
$ [x^m]F = f(m) = \sum_{i,j} j - i
$ [x^n]F^5 is the answer when the sum of the 5 blocks is n
Since the problem condition is "when the sum is less than or equal to N," the final answer we want to obtain is
$ [x^n] \sum_{n=0}^{\infty} F^5
What does this summing part have to do with dividing by (1-x)?
Dividing by (1-x) means multiplying by [$ \sum_{n=0}^\infty x^n
The product of formal power series is the convolution of a sequence of numbers. Since we are convolving with a sequence of all 1's, the Nth term of the convolution result is the sum of the original sequence up to N
$ \sum_{n=0}^{\infty} F^5 = F^5 / (1-x) = \frac{x^5}{(1-x)^{16}(1+x)^5}
Now that we have determined the formal power series we need to find, the next step is to solve for it
First, define a function that passes through only even/odd dimensions of a formal power series
$ \mathcal{E}(G(x)) = \frac{G(x) + G(-x)}{2}
$ \mathcal{O}(G(x)) = \frac{G(x) - G(-x)}{2}
In short, when mirrored and added together on the x-axis, the odd functions cancel each other out and disappear.
Here, (x) is specified for the sake of explanation, but omitted hereafter, $ G^* = G(-x).
$ [x^n]F = P/Q (Q(0)=1)
When n=0
$ [x^n]F = P(0)
This is the loop termination condition
When n is an even number
$ [x^n]F = [x^n]\mathcal{E}(F)
$ = [x^n](\frac{P}{Q} + \frac{P^*}{Q^*})/2
$ = [x^n](\frac{PQ^* + P^*Q}{QQ^*})/2
$ = [x^n](\frac{\mathcal{E}(PQ^*)}{QQ^*})/2
When n is odd
$ [x^n]F = [x^n]\mathcal{O}(F)
$ = [x^n](\frac{P}{Q} - \frac{P^*}{Q^*})/2
$ = [x^n](\frac{PQ^* - P^*Q}{QQ^*})/2
$ = [x^n](\frac{\mathcal{O}(PQ^*)}{QQ^*})/2
At this time $ QQ^* is an even function
$ Q = q_0 + q_1x + q_2 x^2 + ... ...] and let
$ Q^* = q_0 - q_1x + q_2 x^2 + ... because the terms of odd order disappear when multiplied by
In other words, as a sequence of numbers, the odd-numbered sequence is a sequence of skipped zeros.
We can make a compressed Q' of this.
such as $ Q'(x^2) = QQ^*
Since it's a product of formal power series, it can be implemented by convolving a sequence of numbers, and you can just skip ahead and read it.
Similarly, numerators can be compressed because they are a sequence of skipped numbers.
$ P_e(x^2) = \mathcal{E}(PQ^*)
$ P_o(x^2) = \mathcal{O}(PQ^*) / x
maspy found and used a more compact denominator, probably by searching at hand(misunderstanding)
but since it is an aupart, I used $ \frac{x^5}{(1-x)^{16}(1+x)^5} as I have done so far.
I was mistaken when I saw [1,-2,0,2,-1] in the code below, but the formula was the same
code:python
den = np.array(1,-1, np.int64) for _ in range(5):
This was an expansion of [$ (1-x)^3(1+x)
code:python
In 287: reduce(np.convolve, 1, -1 * 3 + 1, 1, 1) maspy used a fast convolution using FFT, but I was too tired to read that one.
I tried to use np.convolute, but it overflowed int64, so I had no choice but to create my own
Qm: $ Q^*
Just sign-reverse the odd-order coefficients of Q
Qm = Q.copy() Qm[1::2] *= -1
code:python
def solve(N):
Q = reduce(
np.convolve,
1, -1 * 16 + 1, 1 * 5,
np.array(1, dtype=np.int64)) P = np.zeros(6, dtype=np.int64)
def conv(X, Y):
ret = np.zeros(n + m - 1, dtype=np.int64)
for i in range(n):
return ret
while N:
Qm = Q.copy()
QQm = conv(Q, Qm)
PQm = conv(P, Qm)
if N % 2:
else:
N //= 2
---
This page is auto-translated from /nishio/Two Snuke. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.